class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> ans;

        if (digits.empty())
        {
            return ans;
        }

        vector<string> tel = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

        ans.push_back("");

        for (auto digit : digits)
        {
            vector<string> tmp;
            for (auto s : ans)
            {
                for (auto ch : tel[digit - '0'])
                {
                    tmp.push_back(s + ch);
                }
            }
            ans = move(tmp);
        }

        return ans;
    }
};